import random
from typing import List


class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:

        # 插入排序（用于小数组优化）
        def insertion_sort(arr, left, right):
            for i in range(left + 1, right + 1):
                key = arr[i]
                j = i - 1
                # 移动比key大的元素
                while j >= left and arr[j] > key:
                    arr[j + 1] = arr[j]
                    j -= 1
                arr[j + 1] = key

        def quick_sort(arr, left, right):
            # 1. 小数组用插入排序优化（减少递归开销）
            if right - left + 1 <= 10:
                insertion_sort(arr, left, right)
                return

            # 2. 检查子数组是否已有序（修复逻辑错误）
            ordered = True
            for i in range(left, right):  # 检查arr[left..right]是否有序
                if arr[i] > arr[i + 1]:
                    ordered = False
                    break
            if ordered:  # 所有元素检查完后再判断
                return

            # 3. 三数取中法选择基准（保持不变，优化分区平衡）
            mid = left + (right - left) // 2
            # 排序三个位置，取中位数
            if arr[left] > arr[right]:
                arr[left], arr[right] = arr[right], arr[left]
            if arr[left] > arr[mid]:
                arr[left], arr[mid] = arr[mid], arr[left]
            if arr[mid] > arr[right]:
                arr[mid], arr[right] = arr[right], arr[mid]
            # 将中位数移到left位置作为基准
            arr[left], arr[mid] = arr[mid], arr[left]
            pivot = arr[left]

            # 4. 分区过程（保持不变）
            i, j = left, right
            while i < j:
                # 从右找小于pivot的元素
                while i < j and arr[j] >= pivot:
                    j -= 1
                arr[i] = arr[j]
                # 从左找大于pivot的元素
                while i < j and arr[i] <= pivot:
                    i += 1
                arr[j] = arr[i]
            # 基准归位
            arr[i] = pivot

            # 5. 递归排序左右子数组
            quick_sort(arr, left, i - 1)
            quick_sort(arr, i + 1, right)

        quick_sort(nums, 0, len(nums) - 1)
        return nums
